class Solution
{
public:
    Solution() {}
    vector<int> finalPrices(vector<int> &prices)
    {
        int n = prices.size();
        vector<int> result(n);
        vector<int> increaseStack;
        increaseStack.reserve(n);
        for (int i = n - 1; i >= 0; --i)
        {
            int price = prices[i];
            int discountedPrice = price;
            while (!increaseStack.empty())
            {
                if (price >= increaseStack.back())
                {

                    discountedPrice = price - increaseStack.back();
                    break;
                }
                else
                {
                    increaseStack.pop_back();
                }
            }
            increaseStack.push_back(price);
            result[i] = discountedPrice;
        }
        return result;
    }
};